package 中等.数学;

import java.util.ArrayDeque;
import java.util.Deque;

/**
 * 在一根无限长的数轴上，你站在0的位置。终点在target的位置。
 * 你可以做一些数量的移动 numMoves :
 * 每次你可以选择向左或向右移动。
 * 第 i 次移动（从  i == 1 开始，到 i == numMoves ），在选择的方向上走 i 步。
 * 给定整数 target ，返回 到达目标所需的 最小 移动次数(即最小 numMoves ) 。
 * <p>
 * 来源：力扣（LeetCode）
 * 链接：https://leetcode.cn/problems/reach-a-number
 */
public class 到达终点数字_754 {

    public static void main(String[] args) {

        System.out.println(reachNumber2(5));

    }

    /**
     * 广度搜索(内存超出)
     *
     * @param target
     * @return
     */
    public int reachNumber(int target) {
        int i = 1;
        int numMoves = 0;
        Deque<Integer> queue = new ArrayDeque<>();
        queue.addLast(0);
        while (!queue.isEmpty()) {
            numMoves++;
            int size = queue.size();
            while (size-- > 0) {
                Integer num = queue.pollFirst();
                if (num + i == target || num - i == target) {
                    return numMoves;
                }
                queue.addLast(num + i);
                queue.addLast(num - i);
            }

            i++;
        }

        return numMoves;
    }

    /**
     * 数学+分析
     * 题意可以理解为 1,2,n... ，其中 1...n 的数字符合正负可以自由搭配，
     * 使得 sum(1...n) 的累加和要等于 target
     * 可能存在 sum(1...n) > target 的情况，那就需要将 1...n 中某些数字
     * 变成负数累加，具体的，如果负数累加和等于 (sum-target)/2，那么可以
     * 将最后 sum == target
     * 分类讨论：
     * 如果 sum-target 为偶数，1...n 中一定有一个数正好等于 (sum-target)/2
     * 如果 sum-target 为奇数，需要尝试将它变成偶数
     * 最多加上两次 i 可以将 sum-target 变成偶数，因为 i 的变化为 奇偶奇偶
     * 加一次 (sum-target)奇 + 奇 = 偶
     * 加两次 (sum-target)奇 + 偶 + 奇 = 偶
     * 注意：
     * target 是正数还是负数对应答案没有影响，为了方便，设置成正数
     * 可以用二分查找或者解方程优化找到 sum(1...n) >= target 中 n 的最小值
     *
     * @param target
     * @return
     */
    public static int reachNumber2(int target) {
        target = Math.abs(target);
        int numMoves = 0;
        int i = 1, curNum = 0;

        while (curNum < target) {
            curNum += i;
            i++;
            numMoves++;
        }

        if (curNum == target || (curNum - target) % 2 == 0) {
            return numMoves;
        }
        if ((curNum - target + i) % 2 == 0) {
            return numMoves + 1;
        }
        return numMoves + 2;
    }

}
